Search Results

Documents authored by Wadge, William W.

Document
DOI: 10.4230/DagSemProc.08271.1
08271 Abstracts Collection – Topological and Game-Theoretic Aspects of Infinite Computations

Authors: Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)

Abstract
From June 29, 2008, to July 4, 2008, the Dagstuhl Seminar 08271 ``Topological and Game-Theoretic Aspects of Infinite Computations'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, many participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner. 08271 Abstracts Collection – Topological and Game-Theoretic Aspects of Infinite Computations. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hertling_et_al:DagSemProc.08271.1,
  author =	{Hertling, Peter and Selivanov, Victor and Thomas, Wolfgang and Wadge, William W. and Wagner, Klaus},
  title =	{{08271 Abstracts Collection – Topological and Game-Theoretic Aspects of Infinite Computations}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.1},
  URN =		{urn:nbn:de:0030-drops-16555},
  doi =		{10.4230/DagSemProc.08271.1},
  annote =	{Keywords: Automata theory, computability in analysis, dataflow computation, hierarchies, infinite computations, infinite games, reactive systems, specification and verification, topological complexity, Wadge reducibility}
}
Document
DOI: 10.4230/DagSemProc.08271.2
08271 Executive Summary – Topological and Game-Theoretic Aspects of Infinite Computations

Authors: Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)

Abstract
The theory of the infinite behaviour of continuously operating computing devices is of primary importance for several branches of theoretical and practical computer science. In particular, it is fundamental for the verification and synthesis of reactive systems like microprocessors or operating systems, for the understanding of dataflow computation, and for the development of adequate mathematical foundations for exact real computation. The seminar brought together researchers from many different disciplines who are working on theoretical or practical aspects of infinite computations. In this summary we describe the topics, the goals, and the contributions of the seminar.
Cite as

Peter Hertling, Victor Selivanov, Wolfgang Thomas, William W. Wadge, and Klaus Wagner. 08271 Executive Summary – Topological and Game-Theoretic Aspects of Infinite Computations. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hertling_et_al:DagSemProc.08271.2,
  author =	{Hertling, Peter and Selivanov, Victor and Thomas, Wolfgang and Wadge, William W. and Wagner, Klaus},
  title =	{{08271 Executive Summary – Topological and Game-Theoretic Aspects of Infinite Computations}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.2},
  URN =		{urn:nbn:de:0030-drops-16499},
  doi =		{10.4230/DagSemProc.08271.2},
  annote =	{Keywords: Automata theory, computability in analysis, dataflow computation, hierarchies, infinite computations, infinite games, reactive systems, specification}
}
Document
DOI: 10.4230/DagSemProc.08271.5
General Logic Programs as Infinite Games

Authors: Chrysida Galanaki, Panos Rondogiannis, and William W. Wadge

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)

Abstract
In [vE86] M.H. van Emden introduced a simple game semantics for definite logic programs. Recently [RW05,GRW05], the authors extended this game to apply to logic programs with negation. Moreover, under the assumption that the programs have a finite number of rules, it was demonstrated in [RW05,GRW05] that the game is equivalent to the well-founded semantics of negation. In this paper we present work-in-progress towards demonstrating that the game of [RW05,GRW05] is equivalent to the well-founded semantics even in the case of programs that have a countably infinite number of rules. We argue however that in this case the proof of correctness has to be more involved. More specifically, in order to demonstrate that the game is correct one has to define a refined game in which each of the two players in his first move makes a bet in the form of a countable ordinal. Each ordinal can be considered as a kind of clock that imposes a "time limit" to the moves of the corresponding player. We argue that this refined game can be used to give the proof of correctness for the countably infinite case.
Cite as

Chrysida Galanaki, Panos Rondogiannis, and William W. Wadge. General Logic Programs as Infinite Games. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{galanaki_et_al:DagSemProc.08271.5,
  author =	{Galanaki, Chrysida and Rondogiannis, Panos and Wadge, William W.},
  title =	{{General Logic Programs as Infinite Games}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.5},
  URN =		{urn:nbn:de:0030-drops-16519},
  doi =		{10.4230/DagSemProc.08271.5},
  annote =	{Keywords: Infinite Games, Negation in Logic Programming, Well-Founded Semantics}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact